package ahu.zdw.com;

/**
 * Author: Zhang Dongwei
 * Date: 2022/3/18 22:05
 * 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
 *
 * 请必须使用时间复杂度为 O(log n) 的算法
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/search-insert-position
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * nums = [1,3,5,6], target = 5
 */
public class _35_searchInsert {
    public static void main(String[] args) {
        int[] nums = {1, 3};
        int target = 3;
        Solution solution = new _35_searchInsert().new Solution();
        int res = solution.searchInsert(nums, target);
        System.out.println(res);
    }

    // 不符合题意，复杂度为O(n)
    class Solution {
        public int searchInsert(int[] nums, int target) {
            int l = nums.length;
            if(nums[l-1]<target) return l;
            if(nums[0]>target) return 0;
            for(int i = 0; i < l; i++){
                if(nums[i] == target)
                    return i;
                if(nums[i]<target && nums[i+1]>target)
                    return i+1;
            }
            return 0;
        }
    }

    // 二分法
    class Solution1 {
        public int searchInsert(int[] nums, int target) {
            int l = nums.length;
            if(nums[l-1]<target) return l;
            if(nums[0]>target) return 0;
            for(int i = 0; i < l; i++){
                if(nums[i] == target)
                    return i;
                if(nums[i]<target && nums[i+1]>target)
                    return i+1;
            }
            return 0;
        }
    }
}
